package q827_largestIsland;

/*
该方法（深度优先）尽管正确 但是超时
 */
public class Solution_1 {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int maxLand = 1;// 因为我们至少会填充一个格子 所以面积至少为1
    int tempArea = 0;
    boolean[][] marked;
    public int largestIsland(int[][] grid) {
        // 此题需要考虑一个问题 也就是如果整个面积都是岛屿
        // 则直接返回m * n的面积即可 flag用于解决该问题
        boolean flag = false;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 遇到0的格子开始操作
                if (grid[i][j] == 0) {
                    // 重置marked
                    marked = new boolean[grid.length][grid[0].length];
                    flag = true;// flag置true
                    tempArea = 0;// 重置temp
                    grid[i][j] = 1;// 将该格子修改
                    dfs(grid, marked, i, j);
                    grid[i][j] = 0;// 修改回
                }
            }
        }

        return flag ? maxLand : grid.length * grid[0].length;
    }

    private void dfs(int[][] grid, boolean[][] marked, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || marked[r][c]) {
            maxLand = Math.max(maxLand, tempArea);
            return;
        }

        // 符合条件的块 则进行对应操作
        tempArea++;
        marked[r][c] = true;

        // 向四个方向继续寻找
        for (int i = 0; i < 4; i++) {
            int next_r = r + dx[i], next_c = c + dy[i];
            dfs(grid, marked, next_r, next_c);
        }
    }


}
